#include<iostream>
using namespace std;
//1.链表的深拷贝
class Node
{
public:
    Node* next;
    Node* random;
    int val;
};
class Solution 
{
public:
    Node* copyRandomList(Node* head) {
        Node* cur = head;
        while (cur)
        {
            Node* pnext = cur->next;
            Node* copy = (Node*)malloc(sizeof(Node));
            copy->val = cur->val;
            cur->next = copy;
            copy->next = pnext;
            cur = pnext;
        }
        cur = head;
        while (cur)
        {
            Node* copy = cur->next;
            if (cur->random == NULL)
            {
                copy->random = NULL;
            }
            else
            {
                copy->random = cur->random->next;
            }
            cur = copy->next;
        }
        cur = head;
        Node* phead = NULL;
        Node* ptail = NULL;
        while (cur)
        {
            Node* copy = cur->next;
            Node* next = copy->next;
            if (phead == NULL)
            {
                phead = ptail = copy;
            }
            else
            {
                ptail->next = copy;
                ptail = copy;
            }
            cur->next = next;
            cur = next;
        }
        return phead;
    }
};
int main()
{
	return 0;
}